namespace HashNormal
{
	template<class K, class V> struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K, V>* _next;

		HashNode(const pair<K, V>& kv)
			:_kv(kv)
			,_next(nullptr)
		{}
	};

	template<class K> struct HashKey
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	template<> struct HashKey<string>
	{
		size_t operator()(const string& s)
		{
			size_t num = 0;
			for (size_t i = 0; i < s.size(); i++)
			{
				num *= 131;
				num += s[i];
			}
			return num;
		}
	};

	template<class K, class V, class Hash = HashKey<K>> class _HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
				return false;

			Hash hash;

			if (_size == _tables.size())
			{
				/*size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;*/
				_HashTable newTable;
				newTable._tables.resize(__stl_next_prime(_tables.size()), nullptr);

				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];

					while (cur)
					{
						Node* next = cur->_next;

						size_t hashi = hash(cur->_kv.first) % newTable._tables.size();
						//int hashi = 0;
						cur->_next = newTable._tables[hashi];
						newTable._tables[hashi] = cur;

						cur = next;
					}

					_tables[i] = nullptr;
				}

				swap(newTable);
			}

			Node* newnode = new Node(kv);
			size_t hashi = hash(kv.first) % _tables.size();
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			_size++;

			return true;
		}

		inline size_t __stl_next_prime(size_t n)
		{
			static const size_t __stl_num_primes = 28;
			static const size_t __stl_prime_list[__stl_num_primes] =
			{
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};

			for (size_t i = 0; i < __stl_num_primes; ++i)
				if (__stl_prime_list[i] > n)
					return __stl_prime_list[i];

			return -1;
		}

		void swap(_HashTable& ht)
		{
			this->_tables.swap(ht._tables);
		}

		bool Erase(const K& key)
		{
			if (!Find(key))
				return false;

			Hash hash;
			size_t hashi = hash(key) % _tables.size();
			Node* cur = _tables[hashi], * prev = nullptr;

			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (cur == _tables[hashi])
					{
						Node* next = cur->_next;
						delete cur;
						_tables[hashi] = next;
						break;
					}
					else
					{
						prev->_next = cur->_next;
						delete cur;
					}
				}
				else
				{
					prev = cur;
				}
				cur = cur->_next;
			}
			_size--;

			return true;
		}

		Node* Find(const K& key)
		{
			if (_size == 0)
				return nullptr;

			Hash hash;
			size_t hashi = hash(key) % _tables.size();

			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
					return cur;
				cur = cur->_next;
			}

			return nullptr;
		}

		void Print()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					cout << cur->_kv.first << ':' << cur->_kv.second << endl;
					cur = cur->_next;
				}
			}
		}

		size_t size() const { return _size; }
		size_t TablesSize() const { return _tables.size(); }
		size_t BucketNum() const 
		{
			size_t num = 0;
			for (size_t i = 0; i < TablesSize(); i++)
				if (_tables[i])
					++num;
			return num;
		}
		size_t MaxBucketLenth() const 
		{
			size_t maxlen = 0;
			for (size_t i = 0; i < TablesSize(); i++)
			{
				Node* cur = _tables[i];
				size_t bktlen = 0;

				while (cur)
				{
					bktlen++;
					cur = cur->_next;
				}

				maxlen = max(maxlen, bktlen);
			}

			return maxlen;
		}

		bool empty() const { return _tables.empty(); }

		~_HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

	private:
		vector<Node*> _tables;
		size_t _size = 0;
	};

	void TestHT3()
	{

		int n = 19000000;
		vector<int> v;
		v.reserve(n);
		srand(time(0));
		for (int i = 0; i < n; ++i)
		{
			//v.push_back(i);
			v.push_back(rand() + i);  // 重复少
			//v.push_back(rand());  // 重复多
		}

		size_t begin1 = clock();
		_HashTable<int, int> ht;
		for (auto e : v)
		{
			ht.Insert(make_pair(e, e));
		}
		size_t end1 = clock();

		cout << "数据个数:" << ht.size() << endl;
		cout << "表的长度:" << ht.TablesSize() << endl;
		cout << "桶的个数:" << ht.BucketNum() << endl;
		cout << "平均每个桶的长度:" << (double)ht.size() / (double)ht.BucketNum() << endl;
		cout << "最长的桶的长度:" << ht.MaxBucketLenth() << endl;
		cout << "负载因子:" << (double)ht.size() / (double)ht.TablesSize() << endl;
	}
}
